package com.dmzc.linkedlist;

import java.util.LinkedHashSet;
import java.util.Set;

//3.Linked-list-cycle
public class LinkedListCycle {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode tail = head;
        tail = tail.next = new ListNode(2);
        tail = tail.next = new ListNode(3);
        ListNode node1 = new ListNode(4);
        tail = tail.next = node1;
        tail = tail.next = new ListNode(5);
        tail = tail.next = new ListNode(6);
        tail = tail.next = new ListNode(7);
        tail = tail.next = new ListNode(8);
        tail = tail.next = new ListNode(9);
        tail.next = node1;
        //判断有没有环的几种算法：
        //设定一定时间，循环检测下一个，超时代表有环；
        //利用set，循环时如果有环则会重复
        //快慢指针的解法
        boolean isCycle = false;
        boolean isCycle1 = false;
        Set<ListNode> set = new LinkedHashSet();
        ListNode curr = head;
        while (curr != null) {
            if (set.contains(curr)) {
                isCycle = true;
                break;
            } else {
                set.add(curr);
            }
            curr = curr.next;
        }
        System.out.println(isCycle);
        //利用快慢指针的方法
        ListNode high = head.next.next;
        ListNode low = head.next;
        for (; low != null && high != null; ) {
            if (low == high) {
                isCycle1 = true;
                break;
            }
            low = low.next;

            if (high.next == null) {
                high = null;
            } else {
                high = high.next.next;
            }
        }
        System.out.println(isCycle1);

    }

}
